/*  slflsdiv.cpp  by K.Tsuru  */ 
// funstion ID = 213    DRADIX, BRADIX
/**********************************************************************
SLong class
m/n
It divides m by a small number n where 0 <= n < ULONG_MAX/m.Radix().
To use IsDiv is better for SInteger.
If rem != NULL the remainder is set on *rem.
***********************************************************************/
#ifndef SN_H
#include "sn.h"
#endif
static const char* const func = "LsDiv";
SLong LsDiv(const SLong& m, ulong n, long* rem){
    if(rem != NULL) *rem = 0;   //remainder = 0
    int m_sign = m.Sign(213);
    if(!n) m.SetError(m.DIVIDED_BY_ZERO, func, 213);
    if(n == 1uL || !m_sign) return m;   // m = 0 or n = 1 --> *rem = 0
    if( n > m.SlOpMaxValue() ){
        m.SetError(m.OUT_OF_RANGE, func, 213);
    }
    int qh = (int)m.aHead, qt = (int)m.aTail;
    ulong rdx = m.Radix();
    SLong quot(m.Type(), 0);    // SInteger is also Ok.

    if(qh <= 1){//The figures of m is two or under, including m < n.
        // s <= (R-1)*R+(R-1) = R^2 -1 < ULONG_MAX
        ulong s = (ulong)m[1]*(ulong)rdx + (ulong)m[0]; //It can be convert to ulong.
        quot.SetLong(long(s/n));
        if(rem != NULL) *rem = m_sign*long(s%n);
        if(quot.Sign()) quot.SetSign(m_sign);
        return quot;
    }
//Here the figures of m is three or over. m >= R^2 > ULONG_MAX/R >= n, then quot != 0
    quot.valloc(m.Size(), -1);
    ulong t = 0;
    const fType* mv = m.ReadFigures();
    fType* qv = quot.figure.Elements();
#ifndef NDEBUG
quot.figure((uint)qh);
#endif
    quot.figure.clear((uint)qh+1u);
    if(qt) quot.figure.clear(0, (uint)qt-1u);
//It begins a calculation.
    int i;  // The type must be "int".
    for(i = qh ; i >= qt; i--){
        t = t*rdx + (ulong)mv[i];
        qv[i] = fType(t/n);
        t = t - qv[i]*n;    //faster than t %= n;
    }
    if(t){  //Here mv[i] = 0.
        for(; t && i >= 0; i--){
            t = t*rdx;
            qv[i] = fType(t/n);
            t = t - qv[i]*n;
        }
        qt = i < 0 ? 0 : i;
    }
//It sets a remainder which has the same sign as m.
    if(rem != NULL) *rem = m_sign*(long)t;
//Get figure positions.
    if(qh){
        while( !qv[qh] && (qh >= 0) ) qh--;
        while( !qv[qt] && (qt <= qh)) qt++;
    }
#ifndef NDEBUG  // quot != 0
assert(qh >= 0 && qv[qh]);
#endif
    quot.SetSign(m_sign);

    quot.aHead = (uint)qh;
    quot.aTail = (uint)qt;

    //It reduces the size if possible.
    if( 2u*(quot.aHead+1) <= quot.figure.size() ) quot.DoCutDown();

    return quot;
}